
           1. (Pomul de Craciun) In noaptea de Ajun, la pomul unui copil sarac
soseste un spiridus care doreste sa aprinda becurile, initial stinse, plasate la
capatul si locurile de ramificare a crengilor. In acest scop spiridusul atinge
cte un bec, efectul fiind schimbarea starii acelui bec (stins  aprins) si ale
tuturor vecinilor sai.
           Sa se determine o modalitate de aprindere a tuturor becurilor, prin
specificarea n ordine a numerelor becurilor atinse de spriridus.
Restrictii tehnice:
  - Numarul n de becuri este cel mult 200 si se citeste de la tastatura.
  - Structura arborelui, a carui radacina este becul 1 situat la radacina pomului,
se citeste din fisierul de intrare. Pe fiecare linie i(1in) se dau nodurile
vecine nodului i, situate imediat mai sus n arbore, ca n exemplul de mai jos.
n  - Iesirea se face n fisierul Craciun.txt, pe o singur[ linie.
Exemplu:
   - pentru n=7 si pomul alaturat, fisierul contine urmatoarele 7 linii:
linia 1:          2 3 4
linia 2:
linia 3:
linia 4:          5 6
linia 5:
linia 6:          7
linia 7:
  - o solutie este: 6 2 5 4 1 2 4 .
=====================================
Solutie (Mihai Stroe)

    Problema se poate rezolva liniar.
    Un arbore poate avea 3 stari:
    1) toate nodurile sunt aprinse si radacina a fost atinsa;
    2) toate nodurile sunt aprinse si radacina nu a fost atinsa;
    3) toate nodurile, cu exceptia radacinii, sunt aprinse si radacina
       nu a fost atinsa.
    Observind aceste stari se pune intrebarea:
    Exista starea "4) : toate nodurile, cu exceptia radacinii, sunt aprinse
    si radacina a fost atinsa" ?
    Raspunsul este negativ deoarece orice arbore in starea 4) ar trebui sa
  aiba un numar impar de subarbori in starea 4), ceea ce nu poate fi
  adevarat ( tinem cont si de faptul ca arborele este finit ).
    Algoritmul porneste de la faptul ca o frunza poate avea starile 1) si 3).
  Stiind starile posibile ale subarborilor unui arbore se pot afla starile
  posibile ale arborelui, astfel:
    - arborele poate avea starea 1) daca toti subarborii pot avea starea 3);
    - arborele poate avea starea 2) daca
               - toti subarborii pot avea cel putin una din starile 1) si 2);
               - exista un numar impar de subarbori care pot fi adusi in
               starea 1);
    - arborele poate avea starea 3) daca
               - toti subarborii pot avea cel putin una din starile 1) si 2);
               - exista un numar par de subarbori care pot fi adusi in
               starea 1).
  Se completeaza starile de la frunze spre radacina.
  Afisarea se realizeaza recursiv, in sens invers.
  Cunoscind starile se pot rezolva si alte probleme:
            - toate modalitatile de aprindere ( exponential, dar mult mai
               rapid decat un backtracking obisnuit );
            - aprinderea cu un numar minim de atingeri (liniar);
            - fiecarui bec fiindu-i asociat un cost, sa se determine
              aprinderea de cost minim/maxim (liniar).

}

var a:array[1..200,1..200]of byte;
    stari:array[1..200,1..3]of byte;
    fii:array[1..200,1..5]of byte;
    frunze,tata,top,top2:array[1..200]of byte;
    i,j,k,l,m,n,nr:longint;
    fi,fo:text;
    s:string;

procedure rec(i,k:byte);
var j,b:byte;
begin
  b:=0;
  case k of
    1:begin
        write(fo,i,' ');
        for j:=1 to top[i] do
            rec(a[i,j],3);
      end;
    2:begin
        if (top[i]-fii[i,1]) mod 2=0 then
           begin
             b:=1;
             while stari[a[i,b],1]+stari[a[i,b],2]<>2 do inc(b);
             rec(a[i,b],1);
             for j:=1 to top[i] do
                 if j<>b then
                 if stari[a[i,j],2]=0 then rec(a[i,j],1)
                                      else rec(a[i,j],2);
           end
           else
           begin
             for j:=1 to top[i] do
                 if stari[a[i,j],2]=0 then rec(a[i,j],1)
                                      else rec(a[i,j],2);
           end;
      end;
    3:begin
        if (top[i]-fii[i,1]) mod 2=1 then
           begin
             b:=1;
             while stari[a[i,b],1]+stari[a[i,b],2]<>2 do inc(b);
             rec(a[i,b],1);
             for j:=1 to top[i] do
                 if j<>b then
                 if stari[a[i,j],2]=0 then rec(a[i,j],1)
                                      else rec(a[i,j],2);
           end
           else
           begin
             for j:=1 to top[i] do
                 if stari[a[i,j],2]=0 then rec(a[i,j],1)
                                      else rec(a[i,j],2);
           end;
      end;
  end;
end;

begin
  write('Introduceti numele fisierului de intrare ');
  readln(s);
  write('Introduceti numarul de becuri ');
  readln(n);
  assign(fi,s);
  assign(fo,'craciun.txt');
  rewrite(fo);
  reset(fi);
  for i:=1 to n do begin stari[i,1]:=1;stari[i,2]:=1;stari[i,3]:=1;end;
  for i:=1 to n do
      begin
        top[i]:=0;
        while not seekeoln(fi)do
          begin
            inc(top[i]);
            read(fi,k);
            tata[k]:=i;
            a[i,top[i]]:=k;
          end;
        readln(fi);
      end;
  for i:=1 to n do
      if top[i]=0 then
         begin
           inc(nr);
           frunze[nr]:=i;
           stari[frunze[nr],1]:=1;
           stari[frunze[nr],2]:=0;
           stari[frunze[nr],1]:=1;
           fii[frunze[nr],1]:=1;
         end;
  top2:=top;
  i:=1;
  while i<>nr+1 do
    begin
      if fii[frunze[i],1]<1 then
         begin
           stari[frunze[i],(fii[frunze[i],2] mod 2)+2]:=0;
         end;
      if stari[frunze[i],3]=0 then stari[tata[frunze[i]],1]:=0;
      if stari[frunze[i],1]+stari[frunze[i],2]=0 then
         begin
           stari[tata[frunze[i]],2]:=0;
           stari[tata[frunze[i]],3]:=0;
         end;
      if stari[frunze[i],1]+stari[frunze[i],2]=2 then inc(fii[tata[frunze[i]],1])
         else if stari[frunze[i],1]=1 then inc(fii[tata[frunze[i]],2]);
      dec(top[tata[frunze[i]]]);
      if top[tata[frunze[i]]]=0 then begin inc(nr);frunze[nr]:=tata[frunze[i]];end;
      inc(i);
    end;
  k:=1;while stari[1,k]<>1 do inc(k);
  top:=top2;
  rec(1,k);
  close(fi);
  close(fo);
end.
